package previous.Test_0314;

import java.util.*;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Blue_bridge {
    //称重砝码
    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n=scan.nextInt();
        int[] a=new int[n];
        int[] dp=new int[n];
        for (int i = 0; i < n; i++) {
            a[i]=scan.nextInt();
        }
        Set<Integer> set=new HashSet<>();
        set.add(0);
        for (int i = 0; i < n; i++) {
            List<Integer> list=new ArrayList<>(set);
            for(int k:list){
                set.add(k+a[i]);
                set.add(Math.abs(k-a[i]));
            }
        }
        System.out.println(set.size()-1);
        scan.close();
    }
    //路径：动态规划
    public static void main2(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int[] dp=new int[2022];
        for (int i = 0; i < 2022; i++) {
            dp[i]=Integer.MAX_VALUE;
        }
        dp[1]=0;
        for (int i = 1; i <=2020 ; i++) {
            //dp[i]表示当前1-j的最短距离或者前一状态到该点最短的距离
            for (int j = i+1; j <=2021 &&(j-i)<=21 ; j++) {
                dp[j]=Math.min(dp[j],dp[i]+lcm(i,j));
            }
        }
        System.out.println(dp[2021]);
        scan.close();
    }
    public static int gcd(int a,int b){
        while(b!=0){
            int tmp=b;
            b=a%b;
            a=tmp;
        }
        return a;
    }
    public static int lcm(int a,int b){
        return (a*b)/gcd(a,b);
    }
    //最长不下降子序列
    //dp[i]:表示以i结尾的最长长度
    public static void main3(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n=scan.nextInt();
        int k=scan.nextInt();
        int[] a=new int[n];
        int ret=1;
        if(n<=10000){
        for (int i = 0; i < n; i++) {
            a[i]=scan.nextInt();
        }
        for (int i = 0; i <=n-k ; i++) {
            int[] tmp=a.clone();
            for (int j = i; j <i+k ; j++) {
                if(i==0){
                    tmp[j]=tmp[i+k];
                }else{
                    tmp[j]=tmp[i-1];
                }
            }
            int len=length(tmp);
            ret=Math.max(len,ret);
        }
        System.out.println(ret);
        }
        scan.close();
    }
    public static int length(int[] a){
        int n=a.length;
        int[] dp=new int[n];
        Arrays.fill(dp,1);
        int ret=1;
        for (int i = 1; i <n ; i++) {
            for (int j = 0; j < i; j++) {
                if(a[j]<=a[i] ){
                    dp[i]=Math.max(dp[i],dp[j]+1);

                }
            }
            ret=Math.max(ret,dp[i]);
        }
        return ret;
    }
    //货物摆放
    public static void main4(String[] args) {
        Scanner scanner=new Scanner(System.in);
        long n=2021041820210418L;
        List<Long> factor=f(n);
        int count=0;
        //确保三个都是质因数
        for (long l:factor) {
            for (long w:factor) {
                if(n%(l*w)==0){
                        count++;
                }
            }
        }
        System.out.println(count);
    }
    //求所有质因数
    public static List<Long> f(long n){
        List<Long> factors=new ArrayList<>();
        for (long i = 1; i <= Math.sqrt(n); i++) {
            if(n%i==0){
                factors.add(i);
                if(i!=n/i){
                    factors.add(n/i);
                }
            }
        }
        return factors;
    }
    //双向排序
    public static void main5(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int m=scanner.nextInt();
        Integer[] a=new Integer[n+1];
        for (int i = 1; i <= n; i++) {
            a[i]=i;
        }
        for (int i = 1; i <= m; i++) {
            int p=scanner.nextInt();
            int q=scanner.nextInt();
            if(p==1){
                Arrays.sort(a,q,n+1);
            }else{
                Arrays.sort(a,1,q+1,(x,y)->y-x);
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.print(a[i]+" ");
        }
    }
    //四平方和
    public static void main6(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        long n=scan.nextLong();
        for (int i = 0; i <= Math.sqrt(n); i++) {
            for (int j = 0; j <= Math.sqrt(n); j++) {
                for (int k = 0; k <=Math.sqrt(n); k++) {
                    long a=n-(i*i+j*j+k*k);
                    long l=(long)Math.sqrt(a);
                    if(l*l==a){
                        System.out.print(i+" "+j+" "+k+" "+l+" ");
                        return;
                    }
                }
            }
        }
        scan.close();
    }

    }

